#include <iostream>
using namespace std;

namespace poly
{
	template<typename T>
	list_iterator<T>::list_iterator(): 
	left(NULL),right(NULL),data(NULL),orig(this) {}

	template<typename T>
	list_iterator<T>::list_iterator(const list_iterator<T>& from): 
	left(from.left),right(from.right),data(from.data),orig(from.orig) {}

	template<typename T>
	list_iterator<T>::list_iterator(T d): 
	left(NULL),right(NULL),orig(this)
	{
		data=new T(d);
	}
	
	template <typename T>
	list_iterator<T>::~list_iterator()
	{
		if (data!=NULL)
			data->~T();
	}


	template<typename T>
	list_iterator<T>& list_iterator<T>::operator++() {
		if (right==NULL) throw "Incrementing end iterator";
		*this=*right;
		return *this;
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator++(int) {
		if (right==NULL) throw "Incrementing end iterator";
		*this=*right;
		return *(this->left);
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator--() {
		if (left==NULL) throw "Decrementing begin iterator";
		*this=*left;
		return *this;
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator--(int) {
		if (left==NULL) throw "Decrementing begin iterator";
		*this=*left;
		return *(this->right);
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator+=(const int d) {
		for (int i=0;i<d;i++) (*this)++;
		return *this;
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator+(const int d) const
	{	
		list_iterator *res=new list_iterator<T>(*this);
		(*res)+=d;
		return *res;
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator-=(const int d) {
		for (int i=0;i<d;i++) (*this)--;
		return *this;
	}

	template<typename T>
	list_iterator<T>& list_iterator<T>::operator-(const int d) const
	{	
		list_iterator *res=new list_iterator<T>(*this);
		(*res)-=d;
		return *res;
	}
	
	template <typename T>
	bool list_iterator<T>::operator ==(const list_iterator<T>& a) const
	{
		return data==a.data;
	}
	
	template <typename T>
	bool list_iterator<T>::operator !=(const list_iterator<T>& a) const
	{
		return data!=a.data;
	}


	template<typename T>
	T& list_iterator<T>::operator *()  const
	{
		return *(this->data);
	}
	
	template<typename T>
	list_iterator<T>& list_iterator<T>::insert_before(const T &p)
	{
		cerr << "iib1" << endl;
		list_iterator<T> *a=new list_iterator<T>(p);
		cerr << "iib2" << endl;
		if (left) left->right=a;
		cerr << "iib3" << endl;
		a->left=left;
		cerr << "iib4" << endl;
		a->right=this;
		cerr << "iib5" << endl;
		left=a;
		cerr << "iib6" << endl;
		return *a;
	}
	
	template<typename T>
	list_iterator<T>& list_iterator<T>::original()
	{
		return *orig;
	}
	
	template<typename T>
	list<T>::list() 
	{
		_begin=new list_iterator<T>();
		_end=_begin;
	}
	
	template <typename T>
	list<T>::list(const T &a)
	{
		list();
		push_back(a);
	}
	
	template <typename T>
	list<T>::list(const list<T> &a)
	{
		_begin=new list_iterator<T>();
		_end=_begin;
		*this=a;
	}

	template<typename T>
	list_iterator<T> list<T>::begin() const
	{
		return *_begin;
	}

	template<typename T>
	list_iterator<T> list<T>::end() const
	{
		return *_end;
	}
	
	template<typename T>
	T& list<T>::operator[](int k) const
	{
		return *(*_begin+k);
	}
	
	template<typename T>
	list<T>& list<T>::operator =(const list<T> &a)
	{
		cerr << "leq1" << endl;
		clear();
		cerr << "leq2" << endl;
		for (list_iterator<T> i=a.begin();i!=a.end();i++) {
			cerr << "leq3" << endl;
			cerr << *i << endl;
			push_back(*i);
			cerr << *this << endl;
			cerr << "leq4" << endl;
		}
		cerr << "leq5" << endl;
		return *this;
	}
	
	template<typename T>
	list_iterator<T> list<T>::get_iterator(int k)
	{
		return (*_begin+k);
	}


	template<typename T>
	int list<T>::size() const
	{
		int res=0;
		for (list<T>::iterator i=begin();i!=end();i++) {
			res++;
		}
		return res;
	}
	
	template<typename T>
	list<T>& list<T>::push_back(const T &p)
	{
		insert_before(end(),p);
		return *this;
	}
	
	template <typename T>
	void list<T>::clear()
	{
		while (begin()!=end()) erase(begin());
	}

	template<typename T>
	void list<T>::reverse()
	{
		for (list_iterator<T> *i=_begin;i!=_end;i=i->left) {
			swap(i->left,i->right);
		}
		_begin->right=_end;
		swap(_begin,_end->left);
		_begin->left=NULL;
	}
	
	template<typename T>
	void list<T>::append(const list<T> &a)
	{
		for (list_iterator<T> i=a.begin();i!=a.end();i++)
		{
			push_back(*i);
		}
	}
	
	template<typename T>
	void list<T>::erase(list_iterator<T> a)
	{
		list_iterator<T>& b=a.original();
		if (b==end()) throw "Trying to erase end"; 
		if (b==begin()) {
			_begin=&(b+1);
			_begin->left=NULL;
		} else {
			(b-1).original().right=b.right;
		}
		(b+1).original().left=b.left;
		b.~list_iterator();
	}

	template <typename T>
	void list<T>::insert_before(list_iterator<T> a,const T &d)
	{
		cerr << "lib1" << endl;
		list_iterator<T> &b=a.original();
		cerr << "lib2" << endl;
		list_iterator<T> &rs=b.insert_before(d);
		cerr << "lib3" << endl;
		if (b==begin()) _begin=rs.orig;
		cerr << "lib5" << endl;
	}

	template<typename T>
	std::ostream& operator <<(std::ostream& out, const list_iterator<T>& a)
	{
		out << (*a);
		return out;
	}

	template<typename T>
	std::istream& operator >>(std::istream& in, list_iterator<T>& a)
	{
		in >> (*a.data);
		return in;
	}
	
	template<typename T>
	std::ostream& operator <<(std::ostream& out, const list<T> &a)
	{
		for (list_iterator<T> i=a.begin(); i!=a.end(); i++) {
			out << i;
		}
		return out;
	}
	
	template<typename T>
	std::istream& operator >>(std::istream& in, list<T>& a)
	{
		int n;
		cin >> n;
		a.clear();
		cerr << "in" << endl;
		for (int i=0;i<n;i++) {
			T k;
			cin >> k;
			cerr <<'!' << k << endl;
			a.push_back(k);
		}
		cerr << "out" << endl;
		return in;
	}
}
